
import java.util.*;

public class Week9 {
    public  void test(){
        System.out.println("task1:"+task1(new int[] {2,7,9},4));
        System.out.println("task2:"+task2(new int[] {0,0,1,0}));
        //System.out.println("task3:"+task3("leetcode",7,20,2,0));
        System.out.println("task3:"+task3("fbxzaad",31,100,3,32));
        String[] strings={"a","b","ab","cde"};
        int[] sulotion=task4(strings);
        System.out.print("task4:[");
        for (int x:sulotion){
            System.out.print(x);
        }
        System.out.print(']');

    }
    public static void main(String[] args){
        Week9 week9 = new Week9();
        week9.test();
    }
    public static int task1(int[] nums,int n){
        Set<Integer> set = new HashSet<>();
        for (int x:nums ) {
            set.add(x);
        }
        boolean flag = true;
        while (flag==true){
            if (set.contains(n)){
                n = n*2;
                flag = true;
            }
            else{
                flag = false;
                return n;
            }
        }
        return n;
    }
    public static List<Integer> task2(int[] nums){
        /*
        第一次遍历，相当于记录好右边的最高得分，此时左边为空也就是0分
        之后遍历每一个元素，当遇到0是左边+1，
        当遇到1时右边-1，并且计算此时左右之和，与最大值进行比较同时

         */
        int max = 0,left=0,right=0;
        for (int i :nums) {
            if (i==1)
                right++;
        }
        List<Integer> res = new ArrayList<>();
        max=right;
        res.add(0);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]==0) {
                left++;
            }else {
                right--;
            }
            if (max<left+right){
                res.clear();
                res.add(i+1);
                max=left+right;
            }else if(max==left+right)
                res.add(i+1);

        }
        return res;
    }
    public static String task3(String s,int power,int modulo,int k,int hashValue){
        int a='a';
        int x=0,n=0;
        char[] ch = s.toCharArray();
        String res="";
        for (int i = 0; i <= ch.length-k; i++) {
            for (int j=0;j<k;j++){
                res=res+ch[i+j];
                n=ch[i+j]-a+1;
                x=(x%modulo+ (n*(int)Math.pow(power,j))%modulo)%modulo;

            }
            if (x%modulo==hashValue)
                break;
            else {
                res="";
                x=0;
            }
        }
        return res;
    }
    //并查集，hashMap并查集模板  fa -->  father
//记录以 m 开头的集合中元素的个数
    private Map<Integer, Integer> fa = new HashMap<>(), size = new HashMap<>();
    //分组，单个集合中元素的最大数量
    int groups, maxSize;

    //查找
    public int find(int idx) {
        if (fa.get(idx) != idx)
            fa.put(idx, find(fa.get(idx)));
        return fa.get(idx);
    }

    //合并
    public void merge(int x, int y) {
        //如果集合中没有y所对应的集合，则直接返回
        if (!fa.containsKey(y)) return;
        int a = find(x);
        int b = find(y);
        //证明已经合并了
        if (a == b) return;
        //将a合并到b
        fa.put(a, b);
        size.put(b, size.get(a) + size.get(b));
        maxSize = Math.max(maxSize, size.get(b));
        //分组减一
        --groups;
    }

    public  int[] task4(String[] words) {
        groups = words.length;
        //初始化
        for (String word : words) {
            int x = 0;
            for (char c : word.toCharArray()) {
                //计算word，所对应的二进制数
                x |= 1 << (c - 'a');
            }
            //添加至并查集
            fa.put(x, x);
            size.put(x, size.getOrDefault(x, 0) + 1);
            maxSize = Math.max(maxSize, size.get(x));
            //排除相同的元素
            if (size.get(x) > 1) --groups;
        }

        //对fa进行遍历
        fa.forEach((x, fx) -> {
            for (int i = 0; i < 26; i++) {
                //增加或删去第i位，所对应的字符
                merge(x, x ^ (1 << i));
                //证明该位上有字符，可以进行替换操作
                if (((x >> i) & 1 )== 1) {
                    for (int j = 0; j < 26; j++) {
                        if (((x >> j) & 1)== 0)
                            //将i位所对应的字符，替换为j位所对应的字符
                            merge(x, x ^ (1 << i) | (1 << j));
                    }
                }
            }
        });
        return new int[]{groups, maxSize};
    }
}
